#include <stdio.h>
#include <stdlib.h>

// B树
/*
如何保证查找效率
策略：
1、 m叉查找树中，规定除了根结点外，任何结点至少有 m/2向上取整 个分叉，即至少 m/2向上取整 - 1 个关键字
2、 m叉查找树中，规定对于任一结点，其所有子树的高度都要相同


B树：
具有以上两个特征查找树
所有结点的孩子个数的最大值称为B树的阶，通常用m表示，即是一棵m阶查找树，
叶子结点和终端结点 ：见图B树.jpg
若根结点不是终端结点，则至少有两棵子树
出根结点外的所有非叶子结点至少有 m/2向上取整 棵子树，即至少含有 m/2向上取整 - 1 个关键字
所有叶子结点都出现在同一层上，且不携带信息


B树的插入删除

插入：
在插入key后，结导致原结点关键字数超过上限，则从中间位置 ( m/2向上取整 ) 将其中的关键字分为两部分，左部分包
含的关键字放在原结点中，右部分包含的关键字放到新结点中，中间位置 ( m/2向上取整 ) 的结点插入原结点的父结点

新元素一定要插到最底层的终端结点中


删除：
若被删除关键字在终端节点，则直接删除该关键字 (要注意节点关键字个数是否低于下限 m/2向上取整 - 1 )

1）兄弟够借。若被删除关键字所在结点删除前的关键字个数低于下限，且与此结点右(或左)兄弟结
点的关键字个数还很宽裕，则需要调整该结点、右(或左)兄弟结点及其双亲结点(父子换位法)
说白了，当右兄弟很宽裕时，用当前结点的后继、后继的后继来填补空缺
当左兄弟很宽裕时，用当前结点的前驱、前驱的前驱来填补空缺

2）兄弟不够借。若被删除关键字所在结点删除前的关键字个数低于下限，且此时与该结点相邻的左、右兄弟结
点的关键字个数均= m/2向上取整- 1，则将关键字删除后与左(或右)兄弟结点及双亲结点中的关键字进行合并

在合并过程中，双亲结点中的关键字个数会减1。若其双亲结点是根结点且关键字个数减少至0 (根结点关键，
字个数为1时，有2棵子树)，则直接将根结点删除，合并后的新结点成为根;若双亲结点不是根结点，且关
键字个数减少到 m/2向上取整 -2,则又要与它自己的兄弟结点进行调整或合并操作，并重复上述步骤，直至符合B
树的要求为止。


若被删除关键字在非终端节点，则用直接前驱或直接后继来替代被删除的关键字，那么对非终端结点的删除就转换为对终端结点的的删除
直接前驱:当前关键字左侧指针所指子树中“最右下”的元素
直接前驱:当前关键字右侧指针所指子树中“最左下”的元素




*/

// B+树 见图 B+树.jpg
/*
类似分块查找


在B+树中，非叶结点不含有该关键字对应记录的存储地址。
可以使一个磁盘块可以包含更多个关键字，使得B+树的阶更大，树高更矮，
读磁盘次数更少，查找更快


*/

int main()
{
    printf("\n\n========================================================================\n\n");

    printf("\n\n========================================================================\n\n");
    return 0;
}